package lc946;
//给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时
//，返回 true；否则，返回 false 。
//
//
//
// 示例 1：
//
//
//输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
//输出：true
//解释：我们可以按以下顺序执行：
//push(1), push(2), push(3), push(4), pop() -> 4,
//push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
//
//
// 示例 2：
//
//
//输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
//输出：false
//解释：1 不能在 2 之前弹出。
//
//
//
//
// 提示：
//
//
// 1 <= pushed.length <= 1000
// 0 <= pushed[i] <= 1000
// pushed 的所有元素 互不相同
// popped.length == pushed.length
// popped 是 pushed 的一个排列
//
// Related Topics 栈 数组 模拟 👍 206 👎 0

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {

    /**
     * 946. 验证栈序列
     * <a href="https://leetcode-cn.com/problems/validate-stack-sequences//"/>
     * push的时候判断能否匹配，能匹配则弹出，然后移动popped下标，如果下标等于等于popped序列长度，则能全部弹出
     * time:O(n) n是序列长度
     * space:O(n) n是栈的大小，也是pushed的序列长度
     * spend: 10m
     */
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int len = pushed.length;
        Deque<Integer> stack = new ArrayDeque<>();
        int j = 0;
        for(int i: pushed){
            stack.push(i);
            while(!stack.isEmpty() && j < len && stack.peek() == popped[j]){
                stack.pop();
                j++;
            }
        }
        return j == len;
    }

}
